package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class lc56 {

    public static void main(String[] args) {
        merge(new int[][]{{1,3},{2,6},{8,10},{15,18}});
    }

    /**
     * Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
     * Output: [[1,6],[8,10],[15,18]]
     */
    public static int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (ints, t1) -> {
            if(ints[0] > t1[0]) return 1;
            else if(ints[0] < t1[0]) return -1;
            else return 0;
        });
        int n = intervals.length;
        List<int[]> retList = new ArrayList<>();
        int[] lastArr = intervals[0];
        for(int i=1;i<n;++i){
            if(isOverlap(lastArr,intervals[i])){
                lastArr = mergeTwo(lastArr,intervals[i]);
            }else{
                retList.add(lastArr);
                lastArr = intervals[i];
            }
        }

        int[][] retArr = new int[retList.size()][2];
        for(int i =0;i<retList.size();++i){
            retArr[i] = retList.get(i);
        }
        return retArr;
    }

    static int[] mergeTwo(int[] num1,int[] num2){
        int newLeft = Math.min(num1[0],num2[0]);
        int newRight = Math.max(num1[1],num2[1]);
        return new int[]{newLeft,newRight};
    }

    static boolean isOverlap(int[] num1,int[] num2){
        return num1[1] >= num2[0];
    }
}
